﻿#define _CRT_SECURE_NO_WARNINGS 1

// https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

#include <iostream>
#include <stack>
using namespace std;

#include <assert.h>

class Node 
{
public:
    int val;
    Node* left;
    Node* right;

    Node() 
    {}

    Node(int _val)
    {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right)
    {
        val = _val;
        left = _left;
        right = _right;
    }
};


class Solution
{
public:
    void InOrderConvert(Node* cur, Node*& prev)
    {
        if (cur == nullptr)
            return;

        // 中序遍历
        InOrderConvert(cur->left, prev);

        // 当前结点的左，指向前⼀个结点
        cur->left = prev;

        // 前⼀个结点的右，指向当前结点
        if (prev)
            prev->right = cur;

        prev = cur;

        InOrderConvert(cur->right, prev);
    }

    Node* treeToDoublyList(Node* root)
    {
        if (root == nullptr)
            return nullptr;

        Node* prev = nullptr;

        InOrderConvert(root, prev);

        // 从根开始往左⾛，找到第⼀个结点
        Node* head = root;
        while (head->left)
        {
            head = head->left;
        }

        // head为第⼀个结点，prev是最后⼀个结点
        // 题⽬要求为循环链表，进⾏⼀些链接

        head->left = prev;
        prev->right = head;

        return head;
    }
};

int main()
{
    // root = [4,2,5,1,3] 
    Node* root = new Node(4);

    root->left = new Node(2);
    root->right = new Node(5);

    root->left->left = new Node(1);
    root->left->right = new Node(3);
                                                    
    auto head = Solution().treeToDoublyList(root);
    auto cur = head;

    do
    {
        cout << cur->val << " ";
        cur = cur->right;
    } while (cur != head);
    
    return 0;
}



